﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/first-bad-version/
/*
题目描述：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：
输入：n = 1, bad = 1
输出：1
*/

bool isBadVersion(int version) {
	// 只做个示范，没有任何作用。
	return true;
}

// 方法1——直接遍历
/*
思路：
直接遍历所有版本，根据题目描述，第一次遇到错误的版本就可以返回。
*/
// 有了以上思路，那我们写起代码来也就水到渠成了：
int firstBadVersion1(int n) {
	int i = 0;
	for (i = 1; i <= n; i++) {
		if (true == isBadVersion(i)) {
			return i;
		}
	}
	return -1;
}
// 时间复杂度：O(n)，n为版本数量，最坏情况下我们需要遍历完所有的版本。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——二分法——极限区间
/*
思路：
由题目描述我们可知正确的版本的左侧所有版本都为正确版本，而错误版本的右侧的所有版本都为错误的版本，
我们可以利用这一点，将我们的区间长度一直缩小到1，具体做法如下：
当isBadVersion(mid) == false时，说明错误的版本只有可能出现在mid右侧，所以转而判断区间[mid + 1, right]，执行left = mid + 1;
当isBadVersion(mid) == true时，说明第一个错误的版本可能出现在mid的左侧，也有可能此时的mid就是第一个错误的版本，
所以转而判断区间[left, mid]，执行right = mid;
最后当left == right时，我们就找到了第一个错误的版本，直接返回left或right都行。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int firstBadVersion2(int n) {
	int left = 0;
	int right = n;
	int mid = 0;
	while (left < right) {
		mid = left + (right - left) / 2;
		if (isBadVersion(mid)) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}
	return left;
}
// 时间复杂度：O(log2N)，N为总的版本数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法3——二分法——直接定位
/*
思路：
由题目描述我们可知：
当 isBadVersion(mid - 1) == false &&  isBadVersion(mid) == false时，说明mid的左端的所有版本都不是错误的，所以查找区间应该转换成[mid + 1, rihgt]，执行left = mid + 1;
当 isBadVersion(mid - 1) == true &&  isBadVersion(mid) == true时，说明mid现在所在的区间正位于错误的版本序列中，为了找到第一个错误的版本，区间应该向左边缩小，缩小成[left, mid];
只有当 isBadVersion(mid - 1) == false &&  isBadVersion(mid) == true时，则说明此时的mid就是第一个错误的版本，直接返回mid即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int firstBadVersion3(int n) {
	int left = 0;
	int right = n;
	int mid = 0;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (isBadVersion(mid - 1) == false && isBadVersion(mid) == false) {
			left = mid + 1;
		}
		else if (isBadVersion(mid - 1) == true && isBadVersion(mid) == true) {
			right = mid;
		}
		else if (isBadVersion(mid - 1) == false && isBadVersion(mid) == true) {
			return mid;
		}
	}
	return -1;
}
// 时间复杂度：O(log2N)，N为总的版本数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法4——二分法找边界
/*
思路：
注意到left移动的条件为：isBadVersion(mid - 1) == false &&  isBadVersion(mid) == false，且移动的方式是left = mid + 1,
所以我们其实可以直接就判断left是否为错误版本，当第一次出现 isBadVersion(left) == true时，就说明left就是第一个出错的版本，
直接返回left即可。
所以我们的操作就变成了：
当isBadVersion(mid - 1) == false &&  isBadVersion(mid) == false时，执行left = mid + 1；
其他情况一律执行right = mid，使区间向左端缩小。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int firstBadVersion4(int n) {
	int left = 0;
	int right = n;
	int mid = 0;
	while (left <= right) {
		if (isBadVersion(left) == true) {
			return left;
		}
		mid = left + (right - left) / 2;
		if (isBadVersion(mid - 1) == false && isBadVersion(mid) == false) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return -1;
}
// 时间复杂度：O(log2N)，N为总的版本数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。
// 这个方法对上一个方法作出的改进是：避免了在left已经指向错误版本后还要不断向左端逼近的繁琐操作。

// 递归版本找边界——用空间换时间
// 先写一个递归版本的找边界函数
int binary_search(int left, int right) {
	if (isBadVersion(left) == true) {
		return left;
	}
	int mid = left + (right - left) / 2;
	if (isBadVersion(mid - 1) == false && isBadVersion(mid) == false) {
		return binary_search(mid + 1, right);
	}
	else {
		return binary_search(left, mid);
	}
}

int firstBadVersion5(int n) {
	return binary_search(1, n);
}

